package cn.edu.zufe.mjt.binary;

/**
 * 二分下标问题
 * 给定一个升序排列的数组 A 和 Q 次询问，每次询问需要找到指定元素 x 在数组中第一次和最后一次出现的位置
 * 不存在则返回 （-1，-1）
 *
 */
public class BinaryIndexQuestions {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7};
        int[] q = {3, 4, 5, 6, 7, 8};
        for (int i : q) {
            int first = binarySearchFirst(arr, i);
            int last = binarySearchLast(arr, i);
            System.out.println(i + " first: " + first + " last: " + last);
        }

    }

    /**
     * 问题分解，查找一个数第一次出现的位置，查找一个数最后一次出现的位置
     */
    public static int binarySearchFirst(int[] arr, int x) {
        // 通解， 以第一次出现为例
        // 1.确定目标点 T
        // 2.划定前缀/后缀区域 P(x<T) / P(x>T)
        // 3.考虑“终局” ：让 L 最终停留在 P 的下一个位置 mid < T 时 L = mid + 1；
        //              让 R 最终停留在 P 的最后一个位置 mid ≥ T 时 R = mid - 1；
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] < x) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (l >= arr.length || arr[l] != x) {
            return -1;
        }
        return l;
    }

    public static int binarySearchLast(int[] arr, int x) {
        // 通解， 以最后一次出现为例
        // 1.确定目标点 T
        // 2.划定前缀/后缀区域 P(x<T) / P(x>T)
        // 3.考虑“终局” ：让 L 最终停留在 P 的第一个位置 mid ≤ T 时 L = mid + 1；
        //              让 R 最终停留在 P 的上一个位置 mid > T 时 R = mid - 1；
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] <= x) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (r < 0 || arr[r] != x) {
            return -1;
        }
        return r;
    }

    // 正确性分析
    // 1.程序是否能结束？
    // mid每次都在 [l,r] 内
    // 指针移动都会让区间缩小
    // 2.是否能找到目标
}
